Obeleži sve kategorije koje odgovaraju problemu

Сортирање и примене

Због својих великих примена сортирање је један од најбоље проучених проблема у рачунарству. Задатак сортирања је да се дата серија уреди у неком траженом поретку (на пример, да се бројеви уреде по величини). Сортирање је у растућем поретку ако је сваки наредни елемент строго већи од претходног а у неопадајућем поретку ако је сваки наредни елемент већи или једнак од претходног. Аналогно се дефинише сортирање у опадајућем и нерастућем поретку.

Сортирање селекцијом

Један од могућих приступа сортирању три променљиве a, b и c јесте тај да прво покушамо да разменама променљивих осигурамо да се најмања вредност налази у променљивој a. За то су нам довољна два поређења и највише две размене. Прво упоређујемо вредности a и b и размењујемо их само ако је b мање од a, чиме осигуравамо да је тренутна вредност a мања или једнака вредности b. Након тога, тренутну вредност променљиве a (то је мања од оригиналних вредности a и b) упоређујемо и са вредношћу c и само ако је c мања од ње, размењујемо их. Тиме је осигурано да тренутна вредност променљиве a буде мања или једнака тренутним вредностима променљивих b и c, при чему ниједна од вредности није изгубљена јер су све време коришћене само размене. На крају, пореде се вредности b и c, и само ако је c мања од вредности b, оне се размењују, чиме се постиже да су све три променљиве сортиране. Дакле овај поступак се може имплементирати на следећи начин (после сваког корака наведен је услов за који сигурно знамо да у том тренутку важи).

if (a > b)
  razmeni(a, b);
// a <= b
if (a > c)
  razmeni(a, c);
// a <= b i a <= c
if (b > c)
  razmeni(b, c);
// a <= b i a <= c i b <= c

Овај алгоритам сортирања назива се сортирање избором најмањег елемента (енгл. selection sort).

Сортирање уметањем

Сортирање уметањем заснива се на идеји да се елементи један по један умећу у сортирани префикс низа. Први елемент a сигурно представља сортирани једночлани низ. Да бисмо обезбедили да прва два елемента представљају сортиран низ, потребно је да заменимо a и b ако је b мање од a. Када су a и b исправно сортирани, тада елемент c треба убацити на његово место. Он се прво пореди са елементом b и ако је већи или једнак од њега, три елемента су већ сортирана како треба. У супротном, размењујемо b и c. Након тога, потребно је још проверити да ли је b сада можда поново мањи од a и ако јесте, разменити a и b. Дакле овај поступак се може имплементирати на следећи начин (после сваког корака наведен је услов за који сигурно знамо да у том тренутку важи).

if (b < a)
  razmeni(a, b);
// a <= b
if (c < b) {
  razmeni(b, c);
  // b <= c, a <= c
  if (b < a)
    razmeni(a, b);
}
// a <= b, b <= c, a <= c

Овај алгоритам сортирања назива се сортирање уметањем (енгл. insertion sort).

Сортирање низа библиотечком функцијом

Најједноставнији начин да се три броја сортирају је да се они сместе у низ и да се примени библиотечка функција за сортирање елемената низа. О низовима и њиховом коришћењу биће више речи у каснијим поглављима ове збирке.

На пример, ако желимо да сортирамо четири бројевне вредности a, b, c и d, можемо формирати четворочлани низ и иницијализовати га на те четири вредности.

int[] niz = {a, b, c, d};

Вредности у низу можемо и учитати са стандардног улаза и тада је приликом декларације низа потребно да означимо да ће низ бити четворочлан.

int niz[4];
cin >> niz[0] >> niz[1] >> niz[2] >> niz[3];

Након што је низ попуњен вредностима, можемо га сортирати библиотечком функцијом sort, на следећи начин.

sort(niz, niz+4);

Алтернативно, могуће је навести и

sort(begin(niz), end(niz));

Сортирање и примене

Због својих великих примена сортирање је један од најбоље проучених проблема у рачунарству. Задатак сортирања је да се дата серија уреди у неком траженом поретку (на пример, да се бројеви уреде по величини). Сортирање је у растућем поретку ако је сваки наредни елемент строго већи од претходног а у неопадајућем поретку ако је сваки наредни елемент већи или једнак од претходног. Аналогно се дефинише сортирање у опадајућем и нерастућем поретку.

Сортирање селекцијом

Један од могућих приступа сортирању три променљиве a, b и c јесте тај да прво покушамо да разменама променљивих осигурамо да се најмања вредност налази у променљивој a. За то су нам довољна два поређења и највише две размене. Прво упоређујемо вредности a и b и размењујемо их само ако је b мање од a, чиме осигуравамо да је тренутна вредност a мања или једнака вредности b. Након тога, тренутну вредност променљиве a (то је мања од оригиналних вредности a и b) упоређујемо и са вредношћу c и само ако је c мања од ње, размењујемо их. Тиме је осигурано да тренутна вредност променљиве a буде мања или једнака тренутним вредностима променљивих b и c, при чему ниједна од вредности није изгубљена јер су све време коришћене само размене. На крају, пореде се вредности b и c, и само ако је c мања од вредности b, оне се размењују, чиме се постиже да су све три променљиве сортиране. Дакле овај поступак се може имплементирати на следећи начин (после сваког корака наведен је услов за који сигурно знамо да у том тренутку важи).

if (a > b)
  razmeni(a, b);
// a <= b
if (a > c)
  razmeni(a, c);
// a <= b i a <= c
if (b > c)
  razmeni(b, c);
// a <= b i a <= c i b <= c

Овај алгоритам сортирања назива се сортирање избором најмањег елемента (енгл. selection sort).

Сортирање уметањем

Сортирање уметањем заснива се на идеји да се елементи један по један умећу у сортирани префикс низа. Први елемент a сигурно представља сортирани једночлани низ. Да бисмо обезбедили да прва два елемента представљају сортиран низ, потребно је да заменимо a и b ако је b мање од a. Када су a и b исправно сортирани, тада елемент c треба убацити на његово место. Он се прво пореди са елементом b и ако је већи или једнак од њега, три елемента су већ сортирана како треба. У супротном, размењујемо b и c. Након тога, потребно је још проверити да ли је b сада можда поново мањи од a и ако јесте, разменити a и b. Дакле овај поступак се може имплементирати на следећи начин (после сваког корака наведен је услов за који сигурно знамо да у том тренутку важи).

if (b < a)
  razmeni(a, b);
// a <= b
if (c < b) {
  razmeni(b, c);
  // b <= c, a <= c
  if (b < a)
    razmeni(a, b);
}
// a <= b, b <= c, a <= c

Овај алгоритам сортирања назива се сортирање уметањем (енгл. insertion sort).

Сортирање низа библиотечком функцијом

Најједноставнији начин да се три броја сортирају је да се они сместе у низ и да се примени библиотечка функција за сортирање елемената низа. О низовима и њиховом коришћењу биће више речи у каснијим поглављима ове збирке.

У језику C# низ се сортира функцијом (тј. процедуром) Array.Sort (аргумент је низ који се сортира и његови елементи се пермутују). На пример, Array.Sort(a); сортира низ a.